1. Field of the Invention
The invention relates to the field of solid model classification and searching. In particular it relates to a method and system for classifying and searching solid models using a learning algorithm.
2. Description of the Related Technology
In order to perform content-based indexing and retrieval of 3D objects, each model must be converted into some collection of features. Previous research on model matching and retrieval has drawn on feature definitions from mechanical design, computer graphics and computer vision literature. Many of these feature-based techniques ultimately use vertex-labeled graphs, whose nodes represent 3D features (or their abstractions) and whose edges represent spatial relations or constraints, between the features. Retrieval and matching is done using some variation of graph matching to assign a numerical value describing the distance between two models.
The computer vision research community has typically viewed shape matching as a problem in 2D [11, 12, 13, 14]. These efforts address a different aspect of the general geometric/solid model matching problem—one in which the main technical challenge is the construction of the models to be matched from image data obtained by cameras.
This has changed in the past several years with the ready availability of 3D models (usually meshes or point clouds) generated from range and sensor data. Thompson et al. [15, 16] reverse engineered designs by generating surfaces and machining feature information from range data collected from machined parts. Jain et al. [17] indexed CAD data based on the creation of “feature vectors” from 2D images. Sipe, Casasent and Talukder [18, 19] used acquired 2D image data to correlate real machined parts with CAD models and performed classification and pose estimation.
There are numerous surveys of feature recognition techniques for CAD [2, 3]; and similarity assessment of 3D models using feature extraction has been addressed [4, 5, 6]. These techniques use an exact representation, as is obtained from a CAD system (i.e., a 3D, watertight boundary representation). However, these representations are proprietary, and their internals vary from system to system. Feature-based descriptions of models also vary by system. Hence, CAD search tools that can perform semantically effective searches using “the lowest common denominator” (e.g., shape) representation are desirable.
Matching 3D shape representations has been widely studied in graphics [7], computer vision [8] and engineering [9]. When shape representations have been used with CAD data, there have been two major shortcomings. First, the current generation of matching techniques has difficulty handling the approximate representations (i.e., polyhedral mesh, point cloud, etc.) that are needed to find sub-patterns in objects or handle data created by 3D scanners. With a few notable exceptions, most researchers assume watertight VRML or shape models. Second, and more importantly, the current generation of search techniques almost exclusively focus on gross or overall shape. In the context of CAD, local features and feature patterns contribute considerably to manufacturing cost, selection of manufacturing processes, produceability and functional parameters of 3D objects. Many objects with similar gross shape can have vastly different functions, costs or manufacturing process specifications.
Once objects are recognized, they can be segmented, decomposed and matched. Matching is frequently accomplished by encoding objects and their decompositions as a graph and analyzing across different graph structures to identify similarity. Graphs and their generalizations are among the most common combinatorial structures in computer science, due in large part to the number of areas of research in which they are applicable. Nayar and Murase extended this work to general 3D objects where a dense set of views was acquired for each object [21]. Eigen-based representations have been widely used in many areas for information retrieval and matching as they offer greater potential for generic shape description and matching. In an attempt to index into a database of graphs, Sossa and Horaud use a small subset of the coefficients of the d2-polynomial corresponding to the Laplacian matrix associated with a graph [22], while a spectral graph decomposition was reported by Sengupta and Boyer for the partitioning of a database of 3D models, in which nodes in a graph represent 3D surface patches [23].
With the ready availability of 3D models from graphics programs and CAD systems, there has been a substantial amount of activity on 3D object recognition and matching in the past 20 years. This body of relevant work is too large to survey in detail in this patent application. Several recent survey papers [8, 9, 7] covers the related work.
Shape-based approaches usually work on a low-level point cloud, mesh or polyhedral model data, such as that produced by digital animation tools or acquired by 3D range scanners. Approaches based on faceted representations include that of Osada et al. [30], which creates an abstraction of the 3D model as a probability distribution of samples from a set of shape functions acting on the model. Hilaga et al. [31] present a method for matching 3D topological models using multi-resolution Reeb graphs. A variant on this is proposed in [32]. A current trend, being pursued by several groups, is the use of different types of shape descriptors (harmonics, Zemike, etc.) to capture shape invariants [33, 34, 35, 36]. The Princeton 3D shape database [37] contains mainly models from 3D graphics and rendering; none of these models are specifically engineering, solid modeling or mechanical CAD oriented.
In general, however, shape matching-based approaches only operate on the gross-shape of a single part and do not operate directly on solid models or consider semantically meaningful engineering information (i.e., manufacturing or design features, tolerances). Retrieval strategies are usually based on a query-by-example or query-by-sketch paradigm.
Unlike shape models, for which only approximate geometry and topology is available, solid models produced by CAD systems are represented by precise boundary representations. When comparing solid models of 3D CAD data, there are two basic types of approaches for content-based matching and retrieval: (1) feature-based techniques and (2) shape-based techniques. The feature-based techniques [38, 2, 39, 3, 40], going back at least as far as 1980 [41], extract engineering features (machining features, form features, etc.) from a solid model of a mechanical part for use in database storage, automated group technology (GT) part coding, etc. graphics. These techniques leverage the ready availability of 3D models on the Internet.
Historically Group Technology (GT) coding was the way to index parts and part families [42]. This facilitated process planning and cell-based manufacturing by imposing a classification scheme (a human-assigned alphanumeric string) to individual machined parts. While there have been a number of attempts to automate the generation of GT codes [43, 44, 45], transition to commercial practice has been limited.
The idea of similarity assessment of 3D models using feature extraction techniques has been discussed [2, 3]. These techniques assume the exact representation (i.e., boundary representation or “B-rep”) for the input models and therefore cannot be used if only an approximate representation (i.e., polyhedral mesh) is available. This is a major shortcoming, especially in designing an archival system, where one may require partial and inexact matching.
There has been recent work on partial matching in the context of 3D data. For instance, Funkhouser et al. successfully employed shape-based search in [46] for 3D models with parts of those models matching a query. In addition, Cornea et al. used approach for many-to-many matching of skeletons of 3D objects in [47] to perform retrieval on those objects.
Elinson et al. [48] used feature-based reasoning for retrieval of solid models for use in variant process planning. Cicirello and Regli [49, 5, 4] examined how to develop graph-based data structures and create heuristic similarity measures among artifacts based on manufacturing features. McWherter et al. [50] integrated these ideas with database techniques to enable indexing and clustering of CAD models based on shape and engineering properties. Other work from the engineering community includes techniques for automatic detection of part families [51] and topological similarity assessment of polyhedral models [52].
Comparing CAD models based on their boundary representations can be difficult due to variability in the underlying feature-based representations. Additional complications are created by differences among the boundary representations used by systems (i.e., some may use all NURBS, some may use a mix of surface types, etc). Using a shape-based approach on voxels, meshes or polyhedral models generated from native CAD representations is one way of reducing these problems.
The 3D-Base Project [53, 54] used CAD models in a voxel representation, which were then used to perform comparisons using geometric moments and other features. Shape classification, scale-space decomposition and classification learning are addressed in recent works [55, 56, 57, 58].
Work out of Purdue [59, 60, 61] has improved on the voxel methods of [53, 54], augmenting them with skeletal structures akin to medial axes or shock graphs. The main accomplishment of the Purdue group is getting these shape-only techniques in a system for query by example.
Despite the many variations on these concepts, there remains a need for improvements in the methods and systems employed for solid model classification and searching.